package org.example.algorithm.graph;

import java.util.LinkedList;
import java.util.Queue;

//多源BFS：994. 腐烂的橘子
public class OrangesRottingSolution {
    public int orangesRotting(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        Queue<int[]> badList = new LinkedList<>();
        int goodNum = 0;
        for (int i=0;i<row;i++) {
            for (int j=0;j<col;j++) {
                if (grid[i][j] == 2) {
                    badList.offer(new int[]{i,j});
                }
                if (grid[i][j] == 1) {
                    goodNum++;
                }
            }
        }
        int ans = 0;
        int[][] directions = new int[][] {{1,0}, {-1,0}, {0,1}, {0,-1}};
        while (goodNum > 0 && !badList.isEmpty()) {
            ans++;
            int size = badList.size();
            for (int i=0;i<size;i++) {
                int[] bad = badList.poll();
                for (int j=0;j<directions.length;j++) {
                    int tempRow = bad[0]+directions[j][0];
                    int tempCol = bad[1]+directions[j][1];
                    if (tempRow>=0 && tempRow<row && tempCol>=0 && tempCol<col && grid[tempRow][tempCol] == 1) {
                        grid[tempRow][tempCol] = 2;
                        badList.offer(new int[] {tempRow, tempCol});
                        goodNum--;
                    }
                }
            }
        }
        return goodNum == 0 ? ans : -1;
    }
}
